/*
https://leetcode.cn/problems/minimum-time-to-collect-all-apples-in-a-tree/description/
*/
--------------------------------------------------------------------------------------

#include <vector>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int MinTime(int n, vector<vector<int>>& Edges, vector<bool>& HasApple) {
        int Res = 0;
        
        // 初始化父节点数组，假设每个节点的初始父节点是它自己
        vector<int> Parent(n);
        for (int i = 0; i < n; ++i) {
            Parent[i] = i;
        }

        // 构建树结构，这里我们假设输入的边总是形成一棵有效的树
        for (const auto& Edge : Edges) {
            Parent[Edge[1]] = Edge[0];
        }

        // 用来记录哪些节点已经被访问过
        unordered_set<int> Uset;

        // 对于每一个有苹果的节点，计算到达该节点并返回根节点所需的最小时间
        for (int i = 0; i < n; ++i) {
            if (HasApple[i]) { // 如果当前节点有苹果
                if (i == 0) continue; // 如果是根节点，则不需要移动

                // 如果父节点还没有被访问过
                if (!Uset.count(Parent[i])) {
                    int T = Parent[i];
                    // 向上追溯直到遇到已经访问过的节点或根节点
                    while (!Uset.count(T) && T != Parent[T]) {
                        Uset.insert(T); // 标记此节点为已访问
                        T = Parent[T]; // 移动到父节点
                        Res += 2; // 每经过一条边，增加2单位时间
                    }
                    // 父节点标记为已访问
                    Uset.insert(Parent[i]);
                }
                // 计算从当前节点移动到父节点再返回的时间
                Res += 2;
                // 将当前节点标记为已访问
                Uset.insert(i);
            }
        }

        return Res;
    }
};